package demo6;

class Trie {

    public static class Node{

		public int pass ;//经过这节点的次数
		public int end;//以这个字符为结尾的次数

		public Node[] nexts ;//多叉树,每个节点都会有很多条路

		//构造方法

		public Node(){
			this.pass = 0;
			this.end = 0;
			this.nexts = new Node[26];//可能会有26条路
		}

	}


       private Node root ;//前缀树的根节点

		public Trie(){
			root = new Node();//创建前缀树这个根节点
		}

		//insert方法---将字符串插入到这颗前缀树中

		public void insert(String words){
			if(words == null){
				return ;
			}
			char[] str = words.toCharArray();//将字符串转化成字符数组

			Node node = root;
			node.pass++;//经过这个节点了
			int path = 0;
			for(int i =0 ;i<str.length;++i){
				path = str[i] - 'a';//该往path这条路走
				if(node.nexts[path] == null){
					node.nexts[path] = new Node();//如果没有这条路就创建这条路
				}
				node = node.nexts[path];
				node.pass++;
			}
			node.end++;

		}

		//搜索这个单词words出现了几次
		public boolean search(String words){
			if(words == null) return false;
			char[] str = words.toCharArray();

			Node node = root;
			int path = 0;
			for(int i =0;i<str.length;++i){
				path = str[i] - 'a' ;//得到是哪条路

				if(node.nexts[path]==null){
					return false;
				}
				node = node.nexts[path];
			}
			return node.end!=0;
		}

		public boolean startsWith(String words){
			if(words == null){
				return false;
			}
			char[] str = words.toCharArray();
			Node node = root;
			int path = 0;
			for(int i =0;i<str.length;++i){
				path = str[i] - 'a';
				if(node.nexts[path] == null){
					return false;
				}
				node = node.nexts[path];
			}
			return true;
		}

	public static void main(String[] args) {
		Trie t = new Trie();
		t.insert("apple");//null
		System.out.println(t.search("apple"));//true
		System.out.println(t.search("app"));//flase
		System.out.println(t.startsWith("app"));//true
		t.insert("app");
		System.out.println(t.search("app"));//true
	}


}
